1. Field of the Invention
The present invention relates to a processor for cyclic coding and cyclic redundancy code check (hereinafter referred to as "CRC"), and particularly relates to a cyclic coding and CRC processor for error detection and correction of the data received in digital communications.
2. Description of the Related Art
Error detection and error correction are techniques used at the receiver to accurately receive the data from the transmitter in digital signal communications. Cyclic coding is a process to generate check bits at the transmitter to facilitate such error detection or error correction at the receiver. It may be used for both error detection and error correction corresponding to the type of generator polynomial and available devices at the receiver.
On the other hand, CRC is a process carried out at the receiver to detect errors in the cyclic coded data as described above. Conventionally, there have been two types of cyclic coding and CRC processor for computerized cyclic coding and CRC corresponding to the degree of the generator polynomial and the number of data bits subjected to cyclic coding. Since the cyclic coding and CRC basically have the same procedure, the following description mainly addresses the cyclic coding.
First of all, the type of the computer, the degree of the generator polynomial and the number of data bits subjected to cyclic coding are defined. Suppose that the computer is an 8 bit microcomputer, the generator polynomial is G(X)=X.sup.3 +X+1, and the number of data subjected to cyclic coding is 50 bits. The 50 bit data for cyclic coding are a.sub.49, a.sub.48, . . . a.sub.1 and a.sub.0, where a.sub.49 is the the most significant bit (MSB).
A cyclic coding and CRC processor in a first conventional example is effective only when the generator polynomial has a low degree and a small number of data bits are processed. As shown in FIG. 6, it comprises a central processing unit (CPU) 600 for operation, data processing and control with a unit of 8 bits, a data memory 620 which stores 50 bits of the data for cyclic coding in order and a table ROM 610 which stores a syndrome table, all of which are connected with a bus 630.
The table ROM 610 stores a syndrome table prepared in advance. For the syndrome table, data polynomials Ai(X)=ai.multidot.X.sup.i for the data which have 50 bits {a.sub.49, . . . a.sub.0 } and whose bits are all "0" except for bit i which is a "1" (i is an integer satisfying 0.ltoreq.i.ltoreq.49) (there exists 50 pieces of such data) are multiplied by X.sup.3 and the products are divided by G(X) with modulo 2. The remainders (=3 bits) of such divisions are stored in the table. The syndrome table substantially has a size of 3 bits.times.50 (50 bytes for a memory of 8 bit units).
Next, refer to the flowcharts of FIGS. 7A and 7B illustrating the processing procedure and Table 1 showing an example of coding with a Z80 assembler.
Firstly, the CPU 600 sets the number of loops C to be 6 (Step 701). Next, it clears the parity register (one of the general purpose registers) inside (Step 702). Then, in Steps 703 to 706, the CPU 600 reads out 8 bit data (a.sub.n to a.sub.n-7 with a n being the MSB; first n=49) from the data memory 620 (input data), shifts the data by one bit and then transmits the MSB to the CY (carry register).
In Step 707, it is judged whether CY=1 or not. If CY is 1, the syndrome value for the hit data an (First n=49) from the table ROM 610 (the lower 3 bits are valid in the 8 bit data (Step 708). Then, the syndrome value and the value at the above parity register are XORed and the result is stored to the above parity register (Step 709).
If CY=0 in Step 707, nothing is performed for it. The CPU 600 performs such bit judgment processing for the remaining bits (a.sub.n-1 to a.sub.n-7 ; n=49) (Steps 710 to 711).
When the processing is completed for all of 8 bits (Step 712), the CPU reads out the next 8 bit data (a.sub.n to a.sub.n-7, n=41) out of the data memory 620 and follows Steps 706 to 712. Then, the CPU 600 performs Steps 704 to 714 for the number of loops (for 48 bits).
Then, in Steps 715 to 721, the remaining two bits are also subjected to the same bit judgment. The lower 3 bits which remain in the above parity register in Steps 722 to 724 are used as the parity bits.
[TABLE 1] __________________________________________________________________________ ****** Cyclic coding (Parity generation) -- Syndrome table method -- Generator polynomial: G(X) = X.sup.3 + X + 1 Data: D[49]-D[0] (50 bits) LD DE, DATA ;DE: Input data address LD HL, SYNDROME ;HL: Syndrome table address LD C, 6 ;C: Number of loops LD A, 0 ;A: Parity register clear EX AF, AF' LOOP1: LD A, (DE) ;A: Input data (8 bits) LD B, 8 ;B: Number of loops LOOP2: SLA A ;MSB - CY JR NC, LOOP3 ;Syndrome operation if CY = 1 EX AF, AF' XOR (HL) ;A .rarw. A XOR (syndrome for D[n]) EX AF, AF' LOOP3: INC L ;Next syndrome table address DEC B JP NZ, LOOP2 INC E ;Next input data address DEC C JP NZ, LOOP1 LD A,(DE) ;A: Input data (2 bits) SLA A ;MSB .fwdarw. CY JR NC, LOOP4 ;Syndrome operation if CY = 1 EX AF, AF' XOR (HL) ;A .rarw. A XOR (syndrome for D[1]) EX AF, AF' LOOP4: INC L ;Next syndrome table address SLA A ;MSB .fwdarw. CY JR NC, LOOP5 ;Syndrome operation if CY = 1 EX AF, AF' XOR (HL) ;A .rarw. A XOR (syndrome for D[0]) LOOP5: ; SYNDROME TABLE SYNDROME: DB Syndrome for D[49] DB Syndrome for D[48] . . DB Syndrome for D[0] __________________________________________________________________________
From the coding example of Table 1, the number of execution states for the first conventional example is calculated to be a value from at least 1855 states to at most 2851 states, depending on whether the data is 1 or 0.
Next, according to a second conventional example, cyclic coding can be made substantially for any number of data bits, provided that the degree of the generator polynomial is not more than twice the number of bits in the applicable general-purpose register. As shown in FIG. 8, a processor according to the present invention comprises a CPU 800 and a data memory 820, which are connected with a bus 830 each other, similarly to the first example.
Referring now to the flowcharts of FIGS. 9A and 9B and a coding example using Z80 assembler in Table 2, the CPU 800 first sets the number of loops E to be 5 (Step 901). Next, it sets the generator polynomial registers (two of the general-purpose registers) in the CPU 800 to have 60H (Step 902). Then, in Step 903, the CPU 800 reads out 8 bit data (a.sub.49 to a.sub.42, with a.sub.49 being the MSB) from the data memory 820 and stores the data to register A (one of the general-purpose registers) inside. In Step 904, the CPU 800 reads out the next 8 bit data (a.sub.n to a.sub.n-7, with a n being the MSB; n=41) from the data memory 820 and stores the data to register B (one of the general-purpose registers) inside.
The above procedure is performed for 8 bits (Step 905). Then, in Step 906, the values of registers A and B are shifted by one bit and the MSB of register B is transmitted to the least significant bit (LSB) of register A and the MSB of register A to the carry register (CY). In Step 907, it is judged whether CY=1 or not. If CY is 1, the values of register A and generator polynomial register are XORed and the result is stored to register A (Step 908). If CY is 0 in Step 907, then the CPU 800 just proceeds to Step 909. Then, the CPU 800 performs such bit judgment processing for the remaining 7 bits (a.sub.48 to a.sub.42) firstly stored to register A (Steps 906 to 910). At this time, the data of register B (a.sub.n to a.sub.n-7 ; n=41) are entirely shifted to register A, and the CPU 800 reads out the following 8 bit data (a.sub.n to a.sub.n-7 ; n=33) from the data memory 820, stores the data to register B and follows Steps 906 to 910. The CPU 800 performs the procedure of Steps 904 to 910 for the number of loops (for 48 bits). Then, in Steps 913 to 919, it performs similar bit judgment for the remaining 2 bits. The higher 3 bits of the value at register A upon completion of processing are the parity bits (Step 920).
[TABLE 2] __________________________________________________________________________ ****** Cyclic coding (parity generation) -- Shift operation method Generator polynomial: G(X) = X.sup.3 + X + 1 data : D[49]-D[0] (50 bits) ****** LD HL, DATA ;HL: Input data address LD C, 60H ;C: Generator polynomial register LD E, 5 ;E: Number of loops LD A, (HL) ;A: Input data LOOP1: INC L ;HL: Next input data address LD B, (HL) ;B: Next input data LD D, 8 LOOP2: RL B ;One bit shifting to the left for registers A & B RL A ;Register B MSB .fwdarw. Register A LSB ;Register A MSB .fwdarw. CY JR NC, LOOP3 ;Operation if CY = 1 XOR C LOOP3: DEC D JP NZ, LOOP2 DEC E JP NZ, LOOP1 INC L LD B,(HL) ;B: Remaining data input (Higher 2 bits are valid) LD D, 10 LOOP4: RL B ;One bit shifting to the left for registers A & B RL A ;Register B MSB .fwdarw. Register A LSB ;Register A MSB .fwdarw. CY JR NC, LOOP5 ;Operation if CY = 1 XOR C LOOP5: DEC D JP NZ, LOOP4 __________________________________________________________________________
From the coding example of Table 2, the number of execution states for the second conventional example is calculated to be a value from 1727 to 2095, depending on whether the data is 1 or 0.
The conventional cyclic coding and CRC processor as described above involves complicated and lengthy processing including judgment process and XOR operation for each bit of data. This limits the time available for other processing such as communication protocol control, and naturally results in an increased cost when a high speed computer is used to reduce time for such processing.